package LeetCode刷题.暑假刷的算法;

import java.util.Vector;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-14 15:35
 * @description: Functions of this class is 找出二叉树中对应值累计和的路径
 **/
public class 二叉树中对应值累计和的路径 {
    public static class TNode {
        int val;
        TNode left, right;
    }

    private static TNode createTree() {
        TNode root = new TNode();

        TNode node1 = new TNode();
        TNode node2 = new TNode();
        TNode node3 = new TNode();
        TNode node4 = new TNode();
        /*
                6
             3    -7
          -1  9
         */
        root.val = 6;
        node1.val = 3;
        node2.val = -7;
        node3.val = -1;
        node4.val = 9;
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node2.right = node3.left = node3.right = node4.left = node4.right = null;
        return root;
    }
    public static void main(String args[]){
        TNode T=createTree();
        System.out.println("找出路径和为8的那条路径：");
        findPath(T,0,8,new Vector<>());
    }

    /**
     *
     * @param T 当前这棵树
     * @param num 当前累计和
     * @param sum 要找的路径的总和
     * @param v 存储路径上每个节点值的集合
     */
    private static void findPath(TNode T, int num, int sum, Vector<Integer> v){
        num+=T.val;
        v.add(T.val);
        if(T.left==null&&T.right==null&&num==sum){
            //说明找到了那条满足路径和的路径
            System.out.print("该路径为：");
            v.stream().forEach(t->System.out.print(t+" "));//打印该路径
        }
        //还没找到 则继续找
        if(T.left!=null){
            findPath(T.left,num,sum,v);
        }
        if(T.right!=null){
            findPath(T.right,num,sum,v);
        }
        //当该路径找到头都不匹配时，进行回退，数值倒减
        num-=v.get(v.size()-1);
        v.remove(v.size()-1);
    }
}